package main

import (
	"fmt"
	"math"
	"math/rand"
	"time"
)

var Chromlength int = 8

const (
	MaxGeneration int     = 100  //最大代数
	PopSize       int     = 10   //样本大小
	Pc            float64 = 0.9  //交叉概率
	Pm            float64 = 0.01 //变异概率
)

var (
	generation      int            //进化次数
	bestIndex       int            //最好个体的下标
	worstIndex      int            //最坏个体的游标
	bestIndividual  Individual     //当前一代中的最好个体
	worstIndividual Individual     ///当前一代中的坏个体
	currentBest     Individual     // 到目前为止的最好个体
	population      [10]Individual //样本
)

type Individual struct {
	chrom   [8]byte //一个个体的染色体
	value   float64 //目标值
	fitness float64 //适应度
}

//生产第一代样品
func generateInitialPopulation() {
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < PopSize; i++ {
		for j := 0; j < Chromlength; j++ {
			if rand.Int()%10 < 5 {
				population[i].chrom[j] = 0 //填充八位二进制数
			} else {
				population[i].chrom[j] = 1
			}
		}
	}
}

//生产下一代样品
func generateNextPopulation() {
	selectionOperator()
	crossoverOperator()
	mutationOperator()
}

//选择算法
func selectionOperator() {
	//fmt.Println(population)
	var index, i int
	var cfitness [10]float64 //存放计算出来的适应度
	p, sum := 0.0, 0.0
	var newpopulation [10]Individual //新样品
	for i = 0; i < PopSize; i++ {    //计算适应度和
		sum += population[i].fitness
	}
	for i = 0; i < PopSize; i++ { //计算适应度的选择概率
		cfitness[i] = population[i].fitness / sum
	}
	for i = 1; i < PopSize; i++ { //计算积累概率
		cfitness[i] = cfitness[i] + cfitness[i-1]
	}
	for i = 0; i < PopSize; i++ {
		p = float64(rand.Intn(1000)) / 1000.0 //随机获取一个概率
		index = 0
		for p > cfitness[index] {
			if index+1 == 10 {
				break
			}
			index++
		}
		newpopulation[i] = population[index] //将该高适应度的样品放入新样品数组
	}
	for i = 0; i < PopSize; i++ {
		population[i] = newpopulation[i] //重新赋值全局样品数组
	}
	//fmt.Println(population)
}

//交叉算法
func crossoverOperator() {
	var index [10]int
	var point int
	var p float64
	//fmt.Println(population)
	for i := 0; i < PopSize; i++ {
		index[i] = i
	}
	for i := 0; i < PopSize; i++ { //随机交换index数组
		point = rand.Int() % (PopSize - i)
		index[i], index[point+i] = index[point+i], index[i]
	}
	//fmt.Println("index : ", index)
	for i := 0; i < PopSize-1; i += 2 {
		p = float64(rand.Intn(1000)) / 1000.0
		if p < Pc {
			point = rand.Intn(Chromlength-1) + 1

			for j := point; j < Chromlength; j++ { //从第point点开始交叉交换
				population[index[i]].chrom[j], population[index[i+1]].chrom[j] = population[index[i+1]].chrom[j], population[index[i]].chrom[j]
			}
		}
	}
	//fmt.Println(population)
}

//变异算法
func mutationOperator() {
	var p float64
	//fmt.Println(population)
	for i := 0; i < PopSize; i++ {
		for j := 0; j < Chromlength; j++ {
			p = float64(rand.Intn(1000)) / 1000.0
			if p < Pm { //将该位的二进制取反
				if population[i].chrom[j] == 0 {
					population[i].chrom[j] = 1
				} else {
					population[i].chrom[j] = 0
				}
			}
		}
	}
	//fmt.Println(population)
}

//计算适应度与目标值
func calculateFitnessValue() {
	var temp1, temp2 int64
	var x1, x2 int64
	for i := 0; i < PopSize; i++ {
		temp1 = decomdeChromosome(population[i].chrom, 0, 4)
		temp2 = decomdeChromosome(population[i].chrom, 4, 8)
		x1, x2 = temp1*temp1, temp2*temp2
		population[i].fitness = float64(x1 + x2)
		population[i].value = float64(x1 + x2)
		//fmt.Println(temp1, "-", temp2, "-", population[i].fitness)
	}
}

//计算二进制对应的十进制值
func decomdeChromosome(bstr [8]byte, left, right int) int64 {
	bslice := bstr[left:right]
	var decimal int64 = 0
	for i := 3; i >= 0; i-- { //累加计算四位二进制的十进制数
		decimal += int64(bslice[i] * byte(math.Pow(2, float64(3-i))))
	}
	return decimal
}

//找目前样品最优个体
func findBestAndWorstIndividual() {
	bestIndividual = population[0]
	worstIndividual = population[0]
	for i := 0; i < PopSize; i++ {
		if population[i].fitness > bestIndividual.fitness {
			bestIndividual = population[i]
			bestIndex = i
		} else if population[i].fitness < worstIndividual.fitness {
			worstIndex = i
			worstIndividual = population[i]
		}
	}
	if generation == 0 {
		currentBest = bestIndividual
	} else {
		if bestIndividual.fitness > currentBest.fitness {
			currentBest = bestIndividual
		}
	}
}

//打印当前样本信息
func outputTestReport() {
	sum := 0.0
	for i := 0; i < PopSize; i++ {
		sum += population[i].value
	}
	avg := sum / float64(PopSize)
	fmt.Printf("gen=%d-avg=%f-best=%f", generation, avg, currentBest.value)
	fmt.Printf("chrom:")
	for i := 0; i < Chromlength; i++ {
		fmt.Printf("%d", currentBest.chrom[i])
	}
	fmt.Println()
}

/////依据某些公式对样本进行评价////
func evalutePopulation() {
	calculateFitnessValue()
	findBestAndWorstIndividual()

}

//判断当前的最好个体与当代最好个体哪个更优
func performEvolution() {
	if bestIndividual.fitness > currentBest.fitness {
		currentBest = population[bestIndex]
	} else {
		population[worstIndex] = currentBest
	}
}
func main() {
	generation = 0
	generateInitialPopulation()
	evalutePopulation()
	for generation < MaxGeneration {
		generation++
		generateNextPopulation()
		evalutePopulation()
		performEvolution()
		outputTestReport()
		if currentBest.fitness == 450 {
			break
		}
	}
}
